class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        return nth(nums, 0, size(nums) - 1, size(nums) - k);
    }

    int nth(vector<int>& nums, int l, int r, int k)
    {
        int n = partition(nums, l, r);
        if (n == k) return nums[n];
        return n > k ? nth(nums, l, n - 1, k) : nth(nums, n + 1, r, k);
    }

    int partition(vector<int>& nums, int l, int r)
    {
        int i = l;
        int j = r;
        while (i < j)
        {
            while (i < j && nums[j] >= nums[l]) --j;
            while (i < j && nums[i] <= nums[l]) ++i;
            if (i < j) swap(nums[i], nums[j]);
        }
        swap(nums[i], nums[l]);
        return i;
    }
};